//
// Created by Administrator on 2021/6/8.
//
#include <vector>
#include <iostream>
#include <numeric>

using namespace std;

class Solution {
public:
    int lastStoneWeightII(vector<int> &stones) {
        // 0-1背包
        // 所有的石头分成两堆  一堆为+ 一堆为-
        // 最后的结果为两堆之差
        // ans = (sum-neg)-neg = sum - 2*neg
        // 为求最小的ans，需要求最大的neg，上限为sum/2 即为背包最大容量
        int stoneSum = accumulate(stones.begin(), stones.end(), 0); // 求和
        int target = stoneSum / 2; // 背包容量
        vector<int> dp(target + 1, 0); // dp数组
        for (auto &x:stones) { // 遍历物品
            for (int i = target; i >= x; --i) { // 倒序遍历背包容量
                dp[i] = max(dp[i], dp[i - x] + x); // 更新方案
            }
        }
        return stoneSum - 2 * dp[target];
    }
};

int main() {
    vector<int> stones{2, 7, 4, 1, 8, 1};
    Solution solution;
    cout << solution.lastStoneWeightII(stones) << endl;
    return 0;
}